package com.wtgroup.demo.mianshi.算法.排序2305;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;

import java.util.Arrays;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/1 18:05
 */
public class HeapSort {

    public static void main(String[] args) {
        Judger.of(() -> {
            int[] nums = RandomUtil.randomArray((int) (Math.random() * 1000 + 1), 0, 100);
            // int[] nums = {2, 9, 11, 17, 24};
            int[] copy1 = Arrays.copyOf(nums, nums.length);
            new HeapSort().sort(copy1);

            int[] copy2 = Arrays.copyOf(nums, nums.length);
            Arrays.sort(copy2);

            if (!Tools.equals(copy1, copy2)) {
                Tools.printArray(nums);
                Tools.printArray(copy1);
                Tools.printArray(copy2);
                return false;
            }
            return true;
        }).setIterCount(1000).start().print();
    }


    public void sort(int[] arr) {
        int N = arr.length;
        // 建堆
        for (int i = N / 2 - 1; i >= 0; i--) {
            percolateDown(arr, i, arr.length);
        }

        // 自堆顶向下, 依次"删除"
        for (int i = N; i > 0; i--) {
            dropTop(arr, i);
        }

    }

    private void dropTop(int[] arr, int heapSize) {
        Tools.swap(arr, 0, heapSize - 1);
        percolateDown(arr, 0, heapSize - 1);
    }

    private void percolateDown(int[] arr, int curr, int heapSize) {
        int backVal = arr[curr];
        int swapChild; // 一开始是左子
        while ((swapChild = (curr * 2 + 1)) < heapSize) {
            // 没有右子或右子比左子小, 都不用考虑右子, 反之, 右子上移
            if (swapChild + 1 < heapSize && arr[swapChild] < arr[swapChild + 1]) {
                swapChild += 1;
            }
            if (arr[swapChild] <= backVal) {
                break;
            }

            arr[curr] = arr[swapChild];
            curr = swapChild;
        }

        arr[curr] = backVal; // 这句一定要放到循环结束后, 内不行, 因为如果到叶子节点, 循环内逻辑执行不到
    }

}
